home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Tech Arsenal 1
/
Tech Arsenal (Arsenal Computer).ISO
/
tek-02
/
sortdemo.zip
/
SDSORT04.INC
< prev
next >
Wrap
Text File
|
1992-04-15
|
5KB
|
122 lines
(*
╔═══════════════════════════════════════════════════════════════════════════╗
║ Turbo Pascal 6.0 Include File : SDSORT04.INC ║
╟───────────────────────────────────────────────────────────────────────────╢
║ Program : SORTDEMO.PAS ║
╟───────────────────────────────────────────────────────────────────────────╢
║ Version : 1.0 ║
╟───────────────────────────────────────────────────────────────────────────╢
║ Copyright (c) 1992 by Jon S. Russell ║
╟───────────────────────────────────────────────────────────────────────────╢
║ Merge sort routine for SORTDEMO.PAS ║
╚═══════════════════════════════════════════════════════════════════════════╝
*)
procedure MergeSort (var Info : InfoType;
First : IndexType;
Last : IndexType);
var
Middle : IndexType; (* middle index in range to sort *)
(*───────────────────────────────────────────────────────────────────────*)
procedure MergeTogether (var Info : InfoType;
LeftFirst : IndexType;
LeftLast : IndexType;
RightFirst : IndexType;
RightLast : IndexType);
(* Merge the two sorted subarrays, List[LeftFirst] .. *)
(* List[LeftLast] and List[RightFirst] .. List[RightLast] *)
(* into a single sorted subarray, List[LeftFirst] .. *)
(* List[RightLast]. *)
var
Temp : InfoType; (* auxiliary array *)
Index : IndexType; (* index into Temp *)
SaveFirst : IndexType; (* saves left first index *)
begin (* MergeTogether *)
(* Initialize indexes before the loop. *)
Index := LeftFirst;
SaveFirst := LeftFirst;
Temp.xElems := Info.xElems; (* for Swap procedure purposes only *)
Temp.yElems := Info.yElems; (* for Swap procedure purposes only *)
Temp.Len := Info.Len; (* for Swap procedure purposes only *)
(* Process while more elements are in both subarrays. *)
while (LeftFirst <= LeftLast) and
(RightFirst <= RightLast) do
begin
if (Info.List[LeftFirst].Key < Info.List[RightFirst].Key)
then
begin (* copy from left half into Temp *)
Temp.List[Index] := Info.List[LeftFirst];
ShowBlock(Temp, Index);
Inc(LeftFirst);
end (* Left element is smaller *)
else
begin (* copy from right half into Temp *)
Temp.List[Index] := Info.List[RightFirst];
ShowBlock(Temp, Index);
Inc(RightFirst);
end; (* Right element is smaller or equal. *)
Inc(Index);
end; (* while -- more elements in loop *)
(* Copy any remaining elements from left half. *)
while (LeftFirst <= LeftLast) do
begin
Temp.List[Index] := Info.List[LeftFirst];
ShowBlock(Temp, Index);
Inc(LeftFirst);
Inc(Index);
end; (* while -- more elements in left half *)
(* Copy any remaining elements from right half. *)
while (RightFirst <= RightLast) do
begin
Temp.List[Index] := Info.List[RightFirst];
ShowBlock(Temp, Index);
Inc(RightFirst);
Inc(Index);
end; (* while -- more elements in right half *)
(* Copy the sorted elements from Temp back into List. *)
for Index := SaveFirst to RightLast do
begin
Info.List[Index] := Temp.List[Index];
ShowBlock(Info, Index);
end; (* for *)
end; (* MergeTogether *)
(*───────────────────────────────────────────────────────────────────────*)
begin (* MergeSort *)
Info.Sorted := false; (* reset flag *)
(* Base Case: Check for empty list or single element. *)
if First < Last then
begin (* General Case *)
(* Cut the array into two halves. *)
Middle := (First+Last) div 2;
(* Sort the left subarray. *)
MergeSort(Info, First, Middle);
(* Sort the right subarray. *)
MergeSort(Info, Middle+1, Last);
(* Merge the two sorted halves together. *)
MergeTogether(Info, (* array to sort *)
First, (* first index in left half. *)
Middle, (* last index in left half. *)
Middle+1, (* first index in right half. *)
Last); (* last index in right half. *)
end; (* General Case *)
Info.Sorted := true; (* set flag *)
end; (* MergeSort *)
(*─────────────────────────────────────────────────────────────────────────*)